Talk:Loader's number
I want to try to disassemble the program and figure out its value. Based on Meows' FGH comparison, it looks like it's at least on the tetrational array level. FB100Z • talk • 00:18, March 11, 2013 (UTC) Can we determine the order type of D(n)? Ikosarakt1 (talk ^ 12:38, April 3, 2013 (UTC) : Calculus of constructions is incredibly strong system. Theoretically, we can do it with every function. Practically, I think we don't have notations able to comprehend that ordinal. LittlePeng9 (talk) 13:13, April 3, 2013 (UTC) : I believe this is the fastest growing computable function ever defined, even faster than Bird's H(n). However, to comprehend its growth rate, I need to know first few terms of sequence. Do you know them? Ikosarakt1 (talk ^ 13:37, April 3, 2013 (UTC) : This function seems to have pretty slow start. D(99) is roughly power tower of height 30000, so calculating values of D(1), D(2) should be easy with loader.c with modified return value. Slow start is due to how program checks statements in CoC - it looks at statements with binary value = E(30416) = 2^^30416. Note the greater than or equals sign - I think that D(99) is probably much greater than 2^^30416. I tried running the program using Gnu C, for some reason I got D(2) = 65536, D(4) = 496, D(5) = 2031616, and negative values for other values of n. LittlePeng9's results are probably more accurate. ::@Ikosarakt1: I believe we can do better than the Calculus of Constructions by diagonolizing over a strong set theory like ZFC. For example, we can let \(f(n) = \sum_1^n g_i(n)\), where \(g_i(n)\) is the \(i\)th provably recursive function of ZFC. To compute \(f(n)\), we can search through all proofs of ZFC until we find a proof that a certain recursive function is total, set \(g_1\) to that function, and evaluate \(g_1\) at \(n\). Then repeat the procedure until we find \(n\) different functions, and sum all of them at \(n\). The resulting \(f(n)\) should grow faster than \(D(n)\). Deedlit11 (talk) 02:49, April 5, 2013 (UTC) ::Your results probably are wrong, because, if I understand definition correctly, D is monotonic. I must admit I had to modify loader.c a bit, because Visual C++ doesn't handle two functions reffering to each other very well. If you ask, I had to directly compute Apply within Subst function. LittlePeng9 (talk) 13:05, April 5, 2013 (UTC) :::I ran the program for higher values, and I also got D(8) = 496 and D(9) = 2031616, with "Segmentation fault" for D(10) and above. I guess the program just doesn't work properly for n < 8. It's interesting, though, that you get the same values for D(4) and D(5) as for D(8) and D(9). Deedlit11 (talk) 00:40, April 6, 2013 (UTC) BB(160;7) vs. Loader's number to Deedlit11: I wrote that BB(160,7) more than Loader's number based on the your comment in LittlePeng's blog "Random Turing machines". Question of ikosarakt1: "Also notice that your machine is very probably not a busy beaver, so BB(160,7) can be incredibly large. So, is it true that BB(160,7)>>Loader's number?" Your answer: "@Ikosarakt1 Yes, I am pretty certain of it." Konkhra (talk) 05:08, May 6, 2013 (UTC) :But we are not sure. It might be a case that my machine is best Busy Beaver (not probable, but still). If we could compute D(n) in reasonable number of states, we would be sure. LittlePeng9 (talk) 12:48, May 6, 2013 (UTC) :Yeah, sorry for the confusion. My above answer was my personal opinion on the growth rate of the busy beaver (in fact, I believe that even BB(100,2) > Loader's number). But we shouldn't put it in the article unless we have proof that it is the case. Deedlit11 (talk) 22:34, May 6, 2013 (UTC) ::OK, I understand Konkhra (talk) 23:33, May 6, 2013 (UTC) Winner Congratulations! Loader! Your number are larger the BIGG :Again, why all the hate towards Hollom? FB100Z • talk • 04:29, May 30, 2013 (UTC) ::No? This number is bottom the bigg in the list. 04:44, May 30, 2013 (UTC) :::It's only our best guess. -- ☁ I want more ⛅ 13:35, May 30, 2013 (UTC) ::::Loader.c uses powerful and complex, but computable, system. I guess it is that large, though it still is guess. LittlePeng9 (talk) 18:29, May 30, 2013 (UTC) S function loses, still, because i see the SCG grows faster still, and the BIGG is below the SCG in the list. Jiawhien (talk) 11:20, May 31, 2013 (UTC) :BIGG is impressive because it's based on an array notation, and it reaches pretty far (we think). I mean, Buchholz hydras and subcubic graphs are really cool, but array notations reaching that far would be truly glorious. FB100Z • talk • 16:43, May 31, 2013 (UTC) ::I found that there exist two types of recursive functions: combinatorial (like SCG(n)) and explicit (like Bird's S(n)). The combinatorials are usually easy to define, but hard to solve. For example, proving even that \(n(3)\geq 64\) requires some effort, while value of S(3) can be quite easily in the FGH. Ikosarakt1 (talk ^ ) 19:25, May 31, 2013 (UTC) More Readable Code I've been working on making the code of the program a bit more readable (it couldn't really be any less readable in the original version). This is where I've got to (download link for txt file containing the code): loader_dot_c_readable_version.txt. This should make it a lot easier to analyse if you can actually see what it's doing! I've tested it for the values that actually work and I got the same as before the edit, so it should do the same thing.DrCeasium (talk) 18:45, June 1, 2013 (UTC) :Do you really understand how D(n) evaluates? If yes, maybe you can explain it less formally? Ikosarakt1 (talk ^ ) 19:34, June 1, 2013 (UTC) :Loader.c is actually standard, read-able program which was later mechanically compressed to 512-bit form. Here is full Loader's entry, containing every part of program, assembled one and compressed one, as well as README file being full explantation of how everything works. LittlePeng9 (talk) 19:55, June 1, 2013 (UTC) Theta function extensions We can define \(\theta_{\alpha+1}(0,\beta) = \theta_{\alpha}(\Omega_{\beta})\) and adopt the normal rules for theta function to higher order theta functions, then limit ordinal of all this will be the first alpha: \(\theta_{\alpha}(0) = \alpha\). Is there a chance that \(f_\alpha(n) \approx D(n)\)? Ikosarakt1 (talk ^ ) 13:19, June 18, 2013 (UTC) Nope, no chance. _Much_ stronger ordinal notations have been defined without going near the ordinal for higher order arithmetic. Deedlit11 (talk) 23:40, June 18, 2013 (UTC) Because the CoC can define second-order arithmetic, does that mean the proof-theoretic ordinal of CoC is larger than that of second-order arithmetic? --Ixfd64 (talk) 00:04, June 19, 2013 (UTC) :I don't think "CoC can define second-order arithmetic" is quite right - what is true is that CoC can define all provably recursive functions of second-order arithmetic. Since a type theory like CoC is quite different from the usual set theories for which proof theoretic ordinals are defined, we may need a different definition of "proof theoretic ordinal" for type theories. However, what we are concerned with are the definable functions of CoC, and since this contains all provably recursive functions of higher order arithmetic, we need to surpass all provably recursive ordinals of higher ordinal arithmetic to get to the level of D(n). Deedlit11 (talk) 01:01, June 19, 2013 (UTC) :Does that mean that its practically impossible to reach CoC level using an array notation or countable ordinal notation that uses only recursion and similar methods? DrCeasium (talk) 17:39, June 22, 2013 (UTC) Values I ran the program through manually for D(1), and I think the reason we,be been getting strange results is that even this is (just) overflowing the storage for an int: the way the pair function works is pretty powerful in comparison to the size of an int. Another reason why it may be broken is that I can't see anywhere where accumulate is actually given a value, until it is defined as pair(some stuff,accumulate), either I'm too used to Java, or that won't work properly. DrCeasium (talk) 08:47, June 23, 2013 (UTC)